// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;
import java.util.ArrayList;
import java.util.Iterator;


class FiniteAutomata implements Iterable<State> {
  public Iterator<State> iterator() {
    return states_.iterator();
  }

  FiniteAutomata() {
    states_ = new ArrayList<State>();
  }
  FiniteAutomata(final State state) {
    states_ = new ArrayList<State>();
    append(state);
  }

  FiniteAutomata reversed() {
    if ( cached_reversed_ == null ) {
      cached_reversed_ = new ReverseFiniteAutomataBuilder().build(this);
    }
    return cached_reversed_;
  }

  State get(final int id) {
    return states_.get(id);
  }

  int size() {
    return states_.size();
  }
  boolean isEmpty() {
    return states_.isEmpty();
  }

  String toDot() {
    return new DotStateVisitor(this).visitAll();
  }


  // this > state.
  void append(final State state) {
    states_.add(state);
  }

  // this > fa.
  void append(final FiniteAutomata fa) {
    states_.addAll(fa.states_);
  }


  //     /---------------v
  // ForkState > fa >   ...
  //
  // greedy: ForkState -> fa, State
  // lazy: ForkState -> State, fa.
  void zeroOrOne(final boolean lazy) {
    if ( isEmpty() ) { throw new RegexException("Internal error"); }

    final int fa_size = size();
    states_.add(0, makeForkState(lazy, 1, 1 + fa_size));
  }

  //     v----------------\
  // ForkState > fa > JumpState   ...
  //      \------------------------^
  //
  // greedy: ForkState -> fa, ...
  // lazy: ForkState -> ..., fa.
  void zeroOrMore(final boolean lazy) {
    if ( isEmpty() ) { throw new RegexException("Internal error"); }

    final int fa_size = size();
    states_.add(0, makeForkState(lazy, 1, 1 + fa_size + 1));
    states_.add(new JumpState(-fa_size - 1));
  }


  // Квантификатор '+' реализуется через (fa)(fa)*, так как алгоритму
  // преобразования автомата к обратному необходимо, чтобы ForkState указывал
  // на состояния, которые идут правее.
  // greedy: ForkState -> fa, ...
  // lazy: ForkState -> ..., fa.
  void oneOrMore(final boolean lazy) {
    if ( isEmpty() ) { throw new RegexException("Internal error"); }
    range(lazy, 1, Parser.RANGE_INFINITE);
  }

  // if max == -1: fa > ...min times... > fa > fa*
  // else: fa > ...min times... > fa > fa? > ...max times... > fa?
  //
  // greedy: ? and * is greedy
  // lazy: ? and * is lazy.
  void range(final boolean lazy, final int min, final int max) {
    if ( isEmpty() ) { throw new RegexException("Internal error"); }
    if ( !( min >= 0 && ( max >= min || max == Parser.RANGE_INFINITE ) ) ) {
      throw new RegexException();
    }

    final boolean max_is_infinite = max == Parser.RANGE_INFINITE;
    if ( min == 0 && max == 1 ) { zeroOrOne(lazy); return; }
    if ( min == 0 && max_is_infinite ) { zeroOrMore(lazy); return; }

    final ArrayList<State> states = new ArrayList<State>();
    for ( int i = 0 ; i < min ; i++ ) {
      states.addAll(states_);
    }

    if ( max_is_infinite ) {
      zeroOrMore(lazy);
      states.addAll(states_);
    } else if ( min != max ) {
      zeroOrOne(lazy);
      for ( int i = min ; i < max ; i++ ) {
        states.addAll(states_);
      }
    }
    states_ = states;
  }

  //     /-----------------------v
  // ForkState > fa > JumpState fa2 > ...
  //                      \------------^
  void alternative(final FiniteAutomata fa2) {
    if ( isEmpty() || fa2.isEmpty() ) {
      throw new RegexException("Internal error");
    }

    final int fa_size = size();
    final int fa2_size = fa2.size();
    states_.add(0, new ForkState(1, 1 + fa_size + 1));
    states_.add(new JumpState(1 + fa2_size));
    states_.addAll(fa2.states_);
  }


  private FiniteAutomata(final ArrayList<State> states) {
    states_ = states;
  }

  private static State makeForkState(final boolean lazy,
                                     final int greedy_high,
                                     final int greedy_low) {
    return lazy ?
           new ForkState(greedy_low, greedy_high) :
           new ForkState(greedy_high, greedy_low);
  }


  private ArrayList<State> states_;
  private FiniteAutomata cached_reversed_;
}
